package qjc.h_二叉树;

import com.二叉树.练习题.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class h10_二叉树的右视图 {
    /**
     * 解题思路：
     * - 使用层序遍历（BFS），逐层处理；
     * - 对每一层，记录该层所有节点；
     * - 将**每层最后一个节点的值**加入结果列表；
     * - 这样就能得到从右往左看时，每层“露出来”的那个节点。
     *
     * @param root
     * @return
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Deque<TreeNode> queue = new LinkedList<>();
        if (root != null) {
            queue.offer(root);
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (i == size - 1) {
                    ans.add(node.val);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return ans;
    }

}
